#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'

void setup(int *a, int n) {
    for (int i = 0; i < n; i++) {
        a[i] = rand();
    }

}

void select_sort(int *a, int left, int right) {
    if (left >= right)return;
    int p = min_element(a + left, a + right + 1) - a;
    swap(a[left], a[p]);
    select_sort(a, left + 1, right);

}

void bubble_sort(int *a, int left, int right) {
    if (left >= right)return;
    for (int i = left; i + 1 <= right; i++) {
        if (a[i] > a[i + 1])swap(a[i], a[i + 1]);
    }
    bubble_sort(a, left, right - 1);

}

void insert_sort(int *a, int left, int right) {
    if (left >= right)return;
    insert_sort(a, left, right - 1);
    int p = upper_bound(a + left, a + right, a[right]) - a;
    if (p == right)return;
    int t=a[right];
    for (int i = right; i > p; i--) {
        a[i] = a[i - 1];

    }
    a[p] =t;

}

int a[100000];

int main() {
    int n = 100000;
    setup(a, n);
    ll start = clock();
    //select_sort(a, 0, n - 1);
    //bubble_sort(a, 0, n - 1);
    insert_sort(a, 0, n - 1);
    ll end = clock();
    cout << 1.0 * (end - start) / CLOCKS_PER_SEC << endl;
    cout << is_sorted(a, a + n) << endl;
    return 0;
}
//select_sort 100000 10.3687
//bubble_sort 100000 36.6632s
//insert_sort 100000 3.28148s